package com.jacklei.ch06;

import sun.awt.image.GifImageDecoder;

import java.awt.geom.FlatteningPathIterator;
import java.util.*;

/*
* 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

 

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class NumberOfIslands {

    //并查集
    class  UnionFind {
        int count;
        int parent[];
        int rank[];

        public UnionFind(char [][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent= new int[m*n];
            rank = new int[m*n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if(grid[i][j] == '1'){
                        parent[i*n+j] = i*n+j;
                        count++;
                    }
                    rank[i*n+j] = 0;
                }
            }
        }
        public int find(int x){
            if(parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        public void union(int x, int y){
            int rootx = find(x);
            int rooty = find(y);
            if(rootx != rooty){
                if(rank[rootx] > rank[rooty]){
                    parent[rooty] = rootx;
                }else if(rank[rootx] < rank[rooty]){
                    parent[rootx] = rooty;
                }else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                count--;
            }
        }

        public int getCount() {
            return count;
        }
    }
   /* class UnionFind {
        int count;
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }

        public int find(int i) {
            if (parent[i] != i) parent[i] = find(parent[i]);
            return parent[i];
        }

        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                --count;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int numIslands3(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        UnionFind uf = new UnionFind(grid);
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    grid[r][c] = '0';
                    if (r - 1 >= 0 && grid[r-1][c] == '1') {
                        uf.union(r * nc + c, (r-1) * nc + c);
                    }
                    if (r + 1 < nr && grid[r+1][c] == '1') {
                        uf.union(r * nc + c, (r+1) * nc + c);
                    }
                    if (c - 1 >= 0 && grid[r][c-1] == '1') {
                        uf.union(r * nc + c, r * nc + c - 1);
                    }
                    if (c + 1 < nc && grid[r][c+1] == '1') {
                        uf.union(r * nc + c, r * nc + c + 1);
                    }
                }
            }
        }

        return uf.getCount();
    }*/


    //广度遍历
    public int numIslands2(char[][] grid){
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length;
        int col = grid[0].length;
        int num = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j] == '1'){
                    grid[i][j] = '0';
                    num++;
                    queue.add(i*col+j);
                    while (!queue.isEmpty()){
                        Integer poll = queue.poll();
                        if (poll != null) {
                            int r = poll/col;
                            int c = poll %col;
                            //上
                            if(r -1 >=0 && grid[r-1][c] == '1'){
                                grid[r-1][c] = '0';
                                queue.add((r-1)*col+c);
                            }
                            //下
                            if(r+1 < row && grid[r+1][c] == '1'){
                                grid[r+1][c] = '0';
                                queue.add((r+1)*col+c);
                            }
                            //左
                            if(c-1 >=0 && grid[r][c-1] == '1'){
                                grid[r][c-1] = '0';
                                queue.add(r*col+c-1);
                            }
                            //右
                            if(c+1 < col && grid[r][c+1] == '1'){
                                grid[r][c+1] = '0';
                                queue.add(r*col+c+1);
                            }
                        }
                    }
                }
            }
        }

        return num;
    }
    //深度遍历
    public int numIslands1(char[][] grid){
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length;
        int col = grid[0].length;
        int num = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j] == '1'){
                    grid[i][j] = '0';
                    num++;
                    dfs(grid,i,j);
                }
            }
        }
        return num;
    }

    private void dfs(char[][] grid, int i, int j) {
        //上
        if( i-1 >=0 && grid[i-1][j] == '1'){
            grid[i-1][j] = '0';
            dfs(grid, i-1, j);
        }
        //下
        if(i+1 < grid.length && grid[i+1][j] =='1'){
            grid[i+1][j] = '0';
            dfs(grid, i+1, j);
        }
        //左
        if(j-1 >=0 && grid[i][j-1] == '1'){
            grid[i][j-1] ='0';
            dfs(grid, i, j-1);
        }
        //右
        if(j+1 < grid[0].length && grid[i][j+1] == '1'){
            grid[i][j+1] = '0';
            dfs(grid, i , j+1);
        }
    }

    public static void main(String[] args) {
        NumberOfIslands n = new NumberOfIslands();
        System.out.println(n.numIslands2(new char[][]{
                {'1','1','0','0','0'},
                {'1','1','0','0','0'},
                {'0','0','1','0','0'},
                {'0','0','0','1','1'}
        }));
        //[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
    }
    public int numIslands(char[][] grid) {
        HashSet<Info> infos = new HashSet<>();

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') infos.add(new Info(i,j));
            }
        }
        int ans = 0 ;
        Info cur =null;
        if(infos.iterator().hasNext()){
            cur =infos.iterator().next();
        }else return ans;
        //ans = getNum(infos,cur,ans);
        while (cur != null){
            ans++;
           remove(infos,cur);
            if(infos.iterator().hasNext()){
                cur =infos.iterator().next();
            }else {
                cur = null;
            }
        }
        return ans;
    }

    public void remove(HashSet infos,Info cur){
        infos.remove(cur);
        int column = cur.column;
        int row = cur.row;
        Info infoU = new Info(column, row + 1);
        Info infoD = new Info(column, row - 1);
        Info infoL = new Info(column - 1, row);
        Info infoR = new Info(column + 1, row);
        boolean u = infos.contains(infoU);
        boolean d = infos.contains(infoD);
        boolean l = infos.contains(infoL);
        boolean r = infos.contains(infoR);
        if(u) {
            infos.remove(infoU);
            remove(infos,infoU);
        }
        if(d) {
            infos.remove(infoD);
            remove(infos,infoD);
        }
        if(l) {
            infos.remove(infoL);
            remove(infos,infoL);
        }
        if(r) {
            infos.remove(infoR);
            remove(infos,infoR);
        }
    }

    private int getNum(HashSet<Info> infos, Info cur,int ans) {
        if(infos.isEmpty()) return 1;
        int column = cur.column;
        int row = cur.row;
        Info infoU = new Info(column, row + 1);
        Info infoD = new Info(column, row - 1);
        Info infoL = new Info(column - 1, row);
        Info infoR = new Info(column + 1, row);
        boolean u = infos.contains(infoU);
        boolean d = infos.contains(infoD);
        boolean l = infos.contains(infoL);
        boolean r = infos.contains(infoR);
        if(u){
            infos.remove(infoU);
            getNum(infos,infoU,ans);
        }
        if(d) {
            infos.remove(infoD);
            getNum(infos,infoD,ans);
        }
        if(l) {
            infos.remove(infoL);
            getNum(infos,infoL,ans);
        }
        if(r) {
            infos.remove(infoR);
            getNum(infos,infoR,ans);
        }
        infos.remove(cur);
        ans++;
        while(infos.iterator().hasNext()){

            cur = infos.iterator().next();
           ans += getNum(infos,cur,ans);

        }
        return ans;
    }
}
class Info{
    public int column;//列
    public int row;//行

    public Info(int column, int row) {
        this.column = column;
        this.row = row;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Info info = (Info) o;
        return column == info.column &&
                row == info.row;
    }

    @Override
    public int hashCode() {
        return Objects.hash(column, row);
    }
}
